# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName : zsj.py
# @Time     : 2024/4/21 22:16
# @Author   : Robot-Zsj
"""
description:

i:
2 1
1 1000
2 1200
1 2 300

o:
2500
"""
import sys

n, m = map(int, input().split())

dist = [[sys.maxsize] * (n + 1) for _ in range(n + 1)]

path = [[-1] * (n + 1) for _ in range(n + 1)]

dic = {}

for i in range(1, n + 1):
    idx, dis = map(int, input().split())

    dic[idx] = i

    dist[0][i] = dis
    dist[i][0] = dis

for i in range(1, m + 1):
    idx1, idx2, dis = map(int, input().split())

    i1 = dic[idx1]
    i2 = dic[idx2]

    dist[i1][i2] = dis
    dist[i2][i1] = dis

ans = sys.maxsize


# floyd算法求解图中任意两个点之间的最短路径
def floyd():
    for k in range(n + 1):
        for i in range(n + 1):
            for j in range(n + 1):
                newDist = dist[i][k] + dist[k][j]

                if newDist < dist[i][j]:
                    dist[i][j] = newDist
                    path[i][j] = k


def dfs(pre, sumDis, used, level):
    global ans

    if level == n:
        ans = min(ans, sumDis + dist[pre][0])
        return

    for i in range(1, n + 1):
        if used[i]:
            continue

        used[i] = True
        dfs(i, sumDis + dist[pre][i], used, level + 1)
        used[i] = False


def main():
    floyd()

    dfs(0, 0, [False] * (n + 1), 0)
    print(ans)


main()
